﻿using System;
using System.Collections.Generic;

namespace MyCollections
{
  public class Dictionary<TKey, TValue>
  {
    private System.Collections.Generic.LinkedList<KeyValuePair<TKey, TValue>>[] _data;
    private int _count;

    public Dictionary()
    {
      _data = new System.Collections.Generic.LinkedList<KeyValuePair<TKey, TValue>>[10];
    }

    public int Count
    {
      get { return _count; }
    }
    public int Length
    {
      get { return _data.Length; }
    }

    public bool Remove(TKey key)
    {
      var record = _data[GetIndex(key)];
      var node = Find(key);
      if (node != null)
      {
        record.Remove(node);
        return true;
      }
      return false;
    }
    public bool TryGetValue(TKey key, out TValue value)
    {
      var node = Find(key);
      if (node != null)
      {
        value = node.Value.Value;
        return true;
      }
      value = default(TValue);
      return false;
    }
    public TValue this[TKey key]
    {
      get
      {
        var node = Find(key);
        if (node == null) throw new KeyNotFoundException();
        return node.Value.Value;
      }
      set
      {
        var record = GetOrCreateRecord(key);
        var node = LinkedList.Find(record, key);
        if (node == null) AddToLinkedList(record, key, value);
        else LinkedList.Replace(record, node, value);
      }
    }
    public void Add(TKey key, TValue value)
    {
      var record = GetOrCreateRecord(key);
      var node = LinkedList.Find(record, key);
      if (node != null) throw new ArgumentException();
      AddToLinkedList(record, key, value);
    }
    public Enumerator GetEnumerator()
    {
      return new Enumerator(this);
    }

    #region ' Enumerator '

    public class Enumerator
    {
      private Dictionary<TKey, TValue> _dictionary;
      private System.Collections.Generic.LinkedListNode<KeyValuePair<TKey, TValue>> _current;

      public Enumerator(Dictionary<TKey, TValue> dictionary)
      {
        _dictionary = dictionary;
        _current = null;
      }

      public void Reset()
      {
        _current = null;
      }

      public System.Collections.Generic.LinkedListNode<KeyValuePair<TKey, TValue>> Current
      {
        get { return _current; }
      }


      public bool MoveNext()
      {
        if (_current == null) // то надо пойти к первому элементу
        {
          for (int i = 0; i < _dictionary.Length; i++)
          {
            if (_dictionary._data[i] != null)
            {
              _current = _dictionary._data[i].First;
              return true;
            }
          }
          return false; // всюду пусто 
        }
        else // что-то уже было , ищем следующий элемент
        {
          if (_current.Next != null)
          {
            _current = _current.Next;
            return true;
          }
          else
          {
            for (var i = _dictionary.GetIndex(_current.Value.Key) + 1; i < _dictionary.Length; i++)
            {
              if (_dictionary._data[i] != null)
              {
                _current = _dictionary._data[i].First;
                return true;
              }
            }
            return false; // а дальше всюду пусто 
          }
        }
      }
    }

    #endregion

    #region ' LinkedList Helpers '

    private static class LinkedList
    {
      public static void Replace(System.Collections.Generic.LinkedList<KeyValuePair<TKey, TValue>> list,
                                 System.Collections.Generic.LinkedListNode<KeyValuePair<TKey, TValue>> node,
                                 TValue value)
      {
        list.Remove(node);
        list.AddLast(new KeyValuePair<TKey, TValue>(node.Value.Key, value));
      }

      public static System.Collections.Generic.LinkedListNode<KeyValuePair<TKey, TValue>> Find(
        System.Collections.Generic.LinkedList<KeyValuePair<TKey, TValue>> list, TKey item)
      {
        var node = list.First;
        while (node != null)
        {
          if (node.Value.Key.Equals(item))
            return node;
          node = node.Next;
        }
        return null;
      }
    }

    #endregion

    private void Expand()
    {
      var oldData = _data;
      _data = new System.Collections.Generic.LinkedList<KeyValuePair<TKey, TValue>>[_data.Length * 2];
      _count = 0;

      foreach (var t in oldData)
      {
        if (t == null) continue;
        foreach (var keyValuePair in t)
          Add(keyValuePair.Key, keyValuePair.Value);
      }
    }
    private System.Collections.Generic.LinkedList<KeyValuePair<TKey, TValue>> GetOrCreateRecord(TKey key)
    {
      var index = GetIndex(key);
      if (_data[index] == null)
      {
        _data[index] = new System.Collections.Generic.LinkedList<KeyValuePair<TKey, TValue>>();
      }
      return _data[index];
    }
    private void AddToLinkedList(System.Collections.Generic.LinkedList<KeyValuePair<TKey, TValue>> record, TKey key, TValue value)
    {
      record.AddLast(new KeyValuePair<TKey, TValue>(key, value));
      _count++;
      if (_count * _count > _data.Length) Expand();
    }
    private int GetIndex(TKey key)
    {
      if (Equals(key, null))
      {
        throw new ArgumentNullException();
      }

      return Math.Abs(key.GetHashCode()) % _data.Length;
    }
    private System.Collections.Generic.LinkedListNode<KeyValuePair<TKey, TValue>> Find(TKey key)
    {
      var record = _data[GetIndex(key)];
      if (record == null) return null;
      return LinkedList.Find(record, key);
    }
  }
}